#include <stdio.h>

//1、顺序查找：在顺序表array[0..n-1]中查找关键字为k的记录，无论查找成功或失败，均通过修改seek_seq参数来
// 返回依次查找的记录位置的序列，seek_seq数组已包含的元素个数等于n；查找成功时返回0，失败时返回-1。函数签名如下：
int seq_search(int array[],int n,int k, int seek_seq[])
{
    for (int i = 0; i < n; i++) {
        if (array[i]==k) {
            seek_seq[i] = i;
            return 0;
        } else{
            seek_seq[i] = i;
        }
    }
    return -1;
}

//2、二分查找：在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，
// 失败时返回-1；无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n。
int bin_search(int array[],int n,int k, int seek_seq[]){
    int low = 0;
    int high = n-1;
    int mid;
    int i= 0;
    //迭代算法：
    while (low<=high){
        mid = (low+high)/2;//除半
        if (array[mid]==k){//查找成功，返回mid索引
            seek_seq[i] = mid;
            return 0;
        }
        else if (array[mid]>k){
            high = mid - 1;
            seek_seq[i] = mid;
        } else{
            low = mid + 1;
            seek_seq[i] = mid;
        }
        i++;
    }
    return -1;
}

int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = 10;
    int k = 8;
    int seek_seq[10];
    int seek_seq0[10];
    for (int j = 0; j < n; j++) {
        seek_seq[j] = -1;
    }
    bin_search(array, n, k, seek_seq);
    for (int i = 0; i < n; i++) {
        if (seek_seq[i] < 0) {
            break;
        }
        printf("%d\n", seek_seq[i]);
    }
    for(int q = 0; q<n;q++){
        seek_seq0[q] = -1;
    }
    seq_search(array, n, k, seek_seq0);
    for (int i = 0; i < n; i++) {
        if (seek_seq[i] < 0) {
            break;
        }
        printf("%d", seek_seq[i]);
    }
    for (int t = 0; t < n; t++) {
        if (seek_seq0[t] < 0) {
            break;
        }
        printf("%d", seek_seq0[t]);
    }
    return 0;
}

